package com.ycy.leetcode.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class BSTcengxu3 {


  public static void main(String[] args) {

    TreeNode treeNode = new TreeNode(500);
    treeNode.left = new TreeNode(100);
    treeNode.left.left = new TreeNode(50);
    treeNode.left.right = new TreeNode(200);

    treeNode.right = new TreeNode(800);
    treeNode.right.left = new TreeNode(700);
    treeNode.right.right = new TreeNode(1000);


    BSTcengxu3 bsTcengxu3 = new BSTcengxu3();
    bsTcengxu3.cengxubianli(treeNode);

    List<List<Integer>> lists = bsTcengxu3.levelOrder(treeNode);
    for (int i = 0; i < lists.size(); i++) {
      List<Integer> integers = lists.get(i);
      for (Integer integer : integers) {
        System.out.print(integer + "\t");
      }
      System.out.println();
    }


  }

  public void cengxubianli(TreeNode root) {

    LinkedList<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
      int size = queue.size();

      for (int i = 0; i < size; i++) {
        TreeNode treeNode = queue.poll();

        System.out.print(treeNode.val + "\t");
        if (treeNode.left != null) queue.add(treeNode.left);
        if (treeNode.right != null) queue.add(treeNode.right);

      }
      System.out.println();
    }

    return;
  }

  public List<List<Integer>> levelOrder(TreeNode root) {
    //  前序遍历 同时要知道当前树的深度

    ArrayList<List<Integer>> list = new ArrayList<>();
    preOrder(list, root, 0);

    return list;
  }

  public void preOrder(List<List<Integer>> list, TreeNode root, int depth) {
    if (root == null) return;

    //添加到列表中去
    put(list, depth, root.val);
    ++depth;
    if (root.left != null) preOrder(list, root.left, depth);
    if (root.right != null) preOrder(list, root.right, depth);

  }

  public void put(List<List<Integer>> lists, int depth, int val) {
    if (depth > lists.size() - 1) {
      lists.add(new ArrayList<>());
    }
    List<Integer> integers = lists.get(depth);
    if (integers == null) {
      integers = new ArrayList<>();
      lists.add(integers);
    }
    integers.add(val);
  }

  static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
      this.val = val;
    }
  }

}
